import { btPrint, PrintableNode } from "hy-algokit";

class Node<T> {
  data: T;
  constructor(value: T) {
    this.data = value;
  }
}

class TreeNode<T> extends Node<T> implements PrintableNode {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
  parent: TreeNode<T> | null = null;
  get isLeft() {
    return !!(this.parent && this.parent.left === this);
  }
  get isRight() {
    return !!(this.parent && this.parent.right === this);
  }

  get value() {
    const data = this.data as Product;
    return data.name + "-" + data.price;
  }
}

class BSTree<T = number> {
  private root: TreeNode<T> | null = null;

  print() {
    return btPrint(this.root);
  }
  // 插入函数
  insert(value: T) {
    const newNode = new TreeNode<T>(value);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  private insertNode(node: TreeNode<T>, newNode: TreeNode<T>) {
    if (newNode.data < node.data) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

  // 先序遍历
  preOrderTraverse() {
    this.preOrderTraverseNode(this.root);
  }

  private preOrderTraverseNode(node: TreeNode<T> | null) {
    if (node !== null) {
      console.log(node.data);
      this.preOrderTraverseNode(node.left);
      this.preOrderTraverseNode(node.right);
    }
  }

  // 中序遍历
  inOrderTraverse() {
    this.inOrderTraverseNode(this.root);
  }
  private inOrderTraverseNode(node: TreeNode<T> | null) {
    if (node !== null) {
      this.inOrderTraverseNode(node.left);
      console.log(node.data);
      this.inOrderTraverseNode(node.right);
    }
  }

  // 后序遍历
  postOrderTraverse() {
    this.postOrderTraverseNode(this.root);
  }

  private postOrderTraverseNode(node: TreeNode<T> | null) {
    if (node !== null) {
      this.postOrderTraverseNode(node.left);
      this.postOrderTraverseNode(node.right);
      console.log(node.data);
    }
  }

  // 层序遍历
  levelOrderTraverse() {
    if (this.root === null) return;

    const queue: TreeNode<T>[] = [];
    queue.push(this.root);

    while (queue.length > 0) {
      const node = queue.shift()!;
      console.log(node.data);

      if (node.left !== null) {
        queue.push(node.left);
      }

      if (node.right !== null) {
        queue.push(node.right);
      }
    }
  }

  // 搜索节点
  search(value: T): boolean {
    return !!this.searchNode(value);
  }

  private searchNode(value: T): TreeNode<T> | null {
    if (this.root === null) return null;
    let current: TreeNode<T> | null = this.root;
    let parent: TreeNode<T> | null = null;
    while (current) {
      if (current.data === value) {
        return current;
      }
      parent = current;
      if (current.data < value) {
        current = current.right;
      } else {
        current = current.left;
      }

      if (current) current.parent = parent;
    }

    return null;
  }

  private getSuccessor(delNode: TreeNode<T>): TreeNode<T> | null {
    let current = delNode.right;
    let successor: TreeNode<T> | null = null;
    while (current) {
      successor = current;
      current = current.left;
      if (current) current.parent = successor;
    }

    // 删除后继节点
    if (successor !== delNode.right) {
      successor!.parent!.left = successor!.left;
      successor!.right = delNode.right;
    }

    successor!.left = delNode.left;

    return successor;
  }

  // 删除节点
  remove(value: T): boolean {
    const current = this.searchNode(value);
    if (!current) return false;

    let replaceNode: TreeNode<T> | null = null;
    if (current.left === null && current.right === null) {
      replaceNode = null;
    } else if (current.right === null) {
      replaceNode = current.left;
    } else if (current.left === null) {
      replaceNode = current.right;
    } else {
      const successor = this.getSuccessor(current);
      replaceNode = successor;
    }

    if (current === this.root) {
      this.root = replaceNode;
    } else if (current.isLeft) {
      current.parent!.left = replaceNode;
    } else {
      current.parent!.right = replaceNode;
    }

    return false;
  }
}

class Product {
  constructor(public name: string, public price: number) {}

  valueOf() {
    return this.price;
  }
}

const bst = new BSTree<Product>();
const p1 = new Product("苹果", 2000);
const p2 = new Product("小米", 3000);
const p3 = new Product("华为", 1000);
const p4 = new Product("三星", 1300);
const p5 = new Product("OPPO", 500);

bst.insert(p1);
bst.insert(p2);
bst.insert(p3);
bst.insert(p4);
bst.insert(p5);
bst.print();

export {};
